مترجم: حبیب الله علیخانی
منبع:راسخون




 

اثبات عدم وجود بن بست

ما اکنون یک بررسی مناسب در مورد عدم وجود بن بست در الگوریتم مسیریابی Opt-bypass مان ارائه می‌کنیم. ما از نتایج موجود استفاده می‌کنیم. این نتایج بوسیله‌ی Duato ارائه شده است و بوسیله‌ی آن نشان داده شده است که الگوریتم مسیریابیOpt-bypass برای مش بندی غیرمنظم LRL ها، بن بست ندارد. مشابه با الگوریتم Opt-y، الگوریتم ما به طور نرمال اجازه می‌دهد تا تنها چرخش های رخ دهد که بوسیله‌ی الگوریتم غربی توصیف شده بوسیله‌ی Glass و Ni ، مورد استفاده قرار گرفته اند. همچنین این رویه، تأیید می‌کند که هیچ سیکلی ایجاد نشده است. اگر LRL در این شبکه نداشته باشد، Opt-bypass به صورت ایده آل مانند Opt-y عمل می‌کنند.
دو قانون اضافی برای Opt-bypass بدین معناست که در برخی مثالها، رابطه‌ی مسیریابی نمی‌تواند به شکل نمودار 3 ، بیان شود. زیرا این انتظار وجود دارد که کانال ورودی باید مطمئن باشند( اگر یک بسته از استفاده کند که تا به مقصدش برسد، در این کانال باقی می‌ماند). هر بسته در این کانال تحت روابط مسیریابی یا تابع انتخاب قرار نمی‌گیرد. تنها این بسته در طول کانال ارسال می‌گردد و یا بوسیله‌ی یک وسیله اتصال یافته به روتور جذب می‌شود. به طور مؤثر، کانال ) یک شبکه‌ی مجزاست و با سایر کانال ها بن بست ایجاد نمی‌کند. این مسئله تنها برای روابط مسیریابی حفظ می‌گردد که بوسیله‌ی آن تعیین می‌شود کدام کانال غربی در زمانی که بسته باید به یک جهت فرستاده شود، مورد استفاده قرار گرفته است. بنابراین، وقتی یک بسته باید به سمت غرب مسیردهی شود، ما انتظار داریم، کانال وردی آن تعیین گردد اگر، این اجازه هنوز وجود داشته باشد که c_(1,w) مورد استفاده قرار گرفته است. در این مورد، روابط مسیریابی ما از معادله‌ی چهارم محاسبه می‌شود. این اثبات هنوز برای ورودی های معادله‌ی چهارم قابل استفاده می‌باشند. این اثبات زیرگروه هایی ایجاد می‌کند که بوسیله‌ی معادله‌ی سوم تأیید می‌شود.
یک شرایط لازم و کافی برای یک رابطه‌ی مسیریابی انطباقی R بدون بن بست شرطی است که در روابط مسیریابی وجود دارد. این روابط دارای هیچ سیکلی در گرافشان نیستند. ما R را به صورت زیرتابع های مسیریابی R1 و زیرروابط Rc تعریف کرده ایم به صورتی که است. در اینجا زیرگروه روابط مسیریابی است () و کانال های موجود دارای رابطه‌ی هستند.
Duato 4 نوع از وابستگی های کانالی را تعریف کردیم: مستقیم، غیر مستقیم، متقاطع مستقیم و متقاطع غیر مستقیم. یک وابستگی مستقیم زمانی ایجاد می‌شود که اجازه داده می‌شود یک بسته از یک کانال به طور مستقیم به کانال دیگر انتقال یابد. یک وابستگی غیر مستقیم در میان کانال های غیر مجاور وجود دارد. در این حالت یک بسته از منبع به مقصد انتقال می‌یابد. وابستگی های غیر مستقیم تنها وقتی ایجاد می‌شود که ما از کنترل جریان حفره کرمی استفاده گرده باشیم زیرا این کنترل اجازه می‌دهد تا بسته ها عدد اختیاری کانال ها را حفظ کنند. استفاده از کنترل جریان ذخیره ای و ارسال شده، امکان حفظ بسته را در بیش از یک کانال، از بین می‌برد. یک وابستگی مقطعی در زمانی رخ می‌دهد که R1 و Rc کانال به اشتراک می‌گذارند. به دلیل اینکه کانال ها میان دو زیر رابطه درOpt-bypass به اشتراک گذاشته نشده اند، ما این نوع از وابستگی را در نظر نگرفته ایم.
اکنون ما می‌خواهیم الگوریتم مسیریابی Opt-bypass را به صورت Rc و R1 توصیف کنیم و نشان دهیم که هیچ سیکلی در گراف وابستگی کانال توسعه یافته‌ی R1 وجود ندارد. یک اثبات که بوسیله‌ی آن ثابت می‌شود Opt-y بدون بن بست است. همچنین ما نشان خواهیم داد که مباحث اضافه شده بوسیله‌ی تئوری ما بر روی خواص و ویژگی های بن بستی آن اثرگذار نبوده اند.

اصل 1: R1 به طور کامل متصل شده است

اثبات: گروه کانال های C1 و R1 که می‌توانند ارسال گردند، عبارتند از . تنها با داشتن این کانال ها، یک بسته می‌تواند ابتدا به غرب جهت دهی گردد و سپس به صورت انطباقی به شمال، جنوب و شرق فرستاده شود. اگر شرط لازم به عنوان ترمینال غربی مورد استفاده قرار گیرد، بنابراین R1 به طور کامل متصل است.

اصل 2. R1 بدون بن بست است

اثبات:
با استفاده از قانون 4، کانال اضافی ما یعنی نمی‌تواند دارای یک وابستگی مستقیم یا غیر مستقیم بر روی هر کانال دیگر، داشته باشد. بنابراین، R1 با استفاده از مدل چرخشی با تقدم غربی، بدون بن بست است.
اصل 3. دارای وابستگی نیست

اثبات:

R1 با استفاده از مدل چرخشی با تقدم غربی، هنوز هم بدون بن بست باقی می‌ماند. قانون چهارم می‌گوید که ) نمی‌تواند وابستگی مستقیم و غیرمستقیمی بر روی سایر کانال ها داشته باشد و بنابراین، دارای سیکل نمی‌باشد.
اصل 4. این اصلاح که برای قید سوم مورد استفاده قرار می‌گیرد، دارای وابستگی سیکلی نیست.
اثبات: شرایطی که تحت آن، و را می‌توان مورد استفاده قرار داد، یک زیرگروه از الگوریتم Opt-y است. از این رو، هیچ وابستگی جدیدی بوجود نمی‌آید.
اصل 5. چرخش های 180 درجه‌ی مجاز در وابستگی سیکلی ایجاد نمی‌شود.

اثبات:

هر 180 درجه می‌تواند در زمانی ایجاد گردد که یک بسته یک LRL را ترک می‌کند و به مقصد می‌رسد. این بدین معناست که بسته می‌تواند تنها چرخشی صفر درجه ایجاد کند و سپس جذب یا تخریب می‌شود. این مسئله تضمین می‌کند که این کانال که بسته در آن چرخش کرده است، نمی‌تواند به دیگری وابسته شود. چرخش های شمال- جنوب و جنوب- شمال، باید از Vc های با اندیس مشابه استفاده کنند تا بدین صورت از بروز وابستگی میان کانال های مورد استفاده برای مسیردهی انطباقی به سمت شمال/ جنوب یا شرق، جلوگیری می‌شود. چرخش های شرق- غرب باید از c_(2,w) استفاده کند. c_(2,w) کانالی است که نمی‌تواند به دیگری وابسته باشد. ما شکل 2 بخش دوم این مقاله را آورده ایم که در ان می‌توان وابستگی کانالی 180 درجه ای را در زمان ایجاد چرخش سیکلی، مشاهده کنید.

تئوری: الگوریتم Opt-bypass بدون بن بست است

اثبات: این بخش بعد از اصول ارائه شده است و یک بخش تکمیلی بر اصولی است که بوسیله‌ی مقالات قبلی ارئه شده است. رابطه‌ی مسیریابی اصلی در Opt-y نشان می‌دهد که این رابطه بدون بن بست است و اصلاحات ما بر این الگوریتم نیر موجب پدید آمدن سیکل نمی‌شود.
ما همچنین یک گراف وابستگی کانالی بسط داده شده برای Opt-bypass در شکل 2 بخش اول این مقاله، آورده ایم. این گراف یک گراف سیکلی است و بیانی مجازی است که در آن بن بست وجود ندارد. ما c_(2,w) را حذف کردیم زیرا این کانال یک کانال سیکلی بدیهی است.

عملکرد الگوریتم

در این بخش، ما نشان دادیم که عملکرد الگوریتم ما چگونه است. این کار با توصیف عدد سناریو، انجام شده است. ما در مورد شرایط دیگر صحبت می‌کنیم و نشان می‌دهیم که چگونه این شرایط یل شرایط موجود در ارتباط هستند. ما بحث خود را به صورت رویه ای مورد بررسی قرار دادیم که در شکل 1 نشان داده شده است. در زیر ما موانع مسیریابی را توصیف می‌کنیم که این قیود بوسیله‌ی بسته های موجود در شبکه همراه هستند. در واقع ما اعمال را در نظر گرفته ایم که در الگوریتم مسیریابی انطباقی ایجاد شده اند. این اعمال که می‌تواند در روتورهای محدود شده، ایجاد شود، به عدد پورت های خروجی وابسته اند. این پورت ها به مسیر مینیمم منظم تکیه دارند. در این مسیرها، بسته به صورت دو یا یک بعدی نمایش داده می‌شود. ما نحوه‌ی محاسبه‌ی پورت های مینیمم غیر منظم را توصیف می‌کنیم، یعنی چگونه یک تصمیم گیری در زمینه‌ی مسیریابی اتخاذ می‌گردد. وقتی هیچ LRLی در شبکه وجود ندارد، الگوریتم Opt-bypass به طور ایده آل به صورت الگوریتم Opt-y عمل می‌کند.
ما اکنون سه سناریوی مورد علاقه را برای شما ارائه می‌دهیم. این سناریوها در الگوریتم ما بهینه سازی می‌شوند. با بهینه سازی آنها، این اطمینان حاصل می‌شود که ترافیک LRLهایی را بدست آورده است و وجود آنها یک مزیت بشمار می‌آید و از ایجاد پورت های غیر فعال جلوگیری می‌کند. همچنین موجب ایجاد LRL در روتورهایی می‌شود که در آنها یک یا دو پورت در یک روتور معین وجود دارد. این روتور معین دارای مسیر بهینه می‌باشد. توجه کنید که اگرتنها یک پورت مینیمم وجود داشته باشد، بسته باید هم اکنون هم در ستون مقصد و یا در سطر مقصد وجود داشته باشد. اگر دو پورت وجود داشته باشد، این دو پورت در هر دو بعد وجود دارند. تنها یک پورت خروجی در هر روتور می‌تواند بوسیله‌ی LRL تحت تأثیر قرار گیرد. در موردی که تنها یک پورت مینیمم وجود دارد و یک انسداد در آن ایجاد گردد، مسیریابی در پیرامون باید اتفاق افتد. در موردی که دو پورت بالقوه وجود داشته باشد، ما دیده ایم که الگوریتم ما همواره راهی را انتخاب می‌کند که مسدود نیست. این مسئله اطمینان حاصل می‌کند که مسیریابی به گره مقصد، انجام می‌شود و بنابراین بن بستی وجود ندارد. در سناریوی ما، ما مسیریابی ترافیکی از منبع های A به C را به مقصدهای D1 و D2 در نظر گرفته ایم. در هر مورد، D1 بیان کننده‌ی وضعیتی است که در آن، منبع دارای یک پورت در مسیر مینیممم منظم است و D2 وضعیتی است که در ان دو پورت بر روی مسیر مینیمم منظم، وجود دارد.

سناریوی A: منبع همپوشانی شده( منبع A)

این مسئله در زمانی رخ می‌دهد که یک بسته در روتور دارای یک LRL، ایجاد شده است. یک پورت خروجی برروی مسیر مینیمم منظم غیر فعال است و بنابراین بسته باید این سد را دور بزند. شکل 1a را ببینید.
مقصد 1: تنها پورت خروجی بر روی مسیر مینیمم منظم غیر فعال شده است. بنابراین، پورت های خروجی در ابعادی که بسته ها نشان داده نمی‌شوند، باید مورد استفاده قرار گیرند. این مسئله موجب پدید آمدن دو خطا می‌شود. یکی پرشی منفرد به ستون یا سطر کناری بدون یک LRL و دیگری، یک پرش برگشتی منفرد به سمت ستون یا سطر مقصد.
مقصد 2: اگر دو پورت بر روی مسیر مینیمم وجود داشته باشد، پورت خروجی دیگری وجود دارد که باید مسدود شود( به دلیل قیود قرارگیری LRL). این بسته در پورتی اختصاص داده می‌شود که دارای خطای پرش نیست.

سناریوی B: پورت پرش بعدی بوسیله‌ی LRL غیر فعال می‌شود( منبع B)

این سناریو در جایی ایجاد می‌شود که مسیر بسته عمود بر یک LRL باشد و پرش بعدی آن را به روتوری با پورت خروجی غیر فعال انتقال می‌دهد. با اجرای یک پرش های تکی، الگوریتم مسیریابی می‌تواند این مشکل را جلوگیری کند. شکل 2a را ببینید.
مقصد 1: تنها پورت خروجی برروی مسیر مینیمم منظم در پرش بعدی غیر فعال است. این عمل ها برای منبع همپوشانی کرده ای که در بالا در مورد آن صحبت شده است، یکسان است. به هر حال، از بروزخطای پرش جلوگیری می‌شود زیرا روتور ارسال کننده‌ی بسته از حالتی که در آن پورت های خروجی روتور مسدود می‌شوند، آگاه است. بسته سپس در طول ستون یا سطر مجاور مسیردهی می‌شود به نحوی که در این حالت همپوشانی ایجاد نمی‌شود و از این رو از ایجاد انسداد نیز جلوگیری می‌شود. علت این موضوع این است که روتور ارسال کننده باید دو پورت بر روی هر مسیر مینیمم منظم بسته داشته باشد. از این رو، در این حالت، هیچ خطای پرشی وجود ندارد.
مقصد 2: اگر دو پورت خروجی بر روی مسیر مینیمم بسته وجود داشته باشد، یکی از پورت ها باید به روتور مسدود شده، هدایت گردد که علت آن قیود قرارگیری است. بنابراین یکی از آنها انتخاب می‌شود و هیچ خطای پرشی بوجود نمی‌آید.

سناریوی C: وجود یک LRL در طول مسیر نرمال ( منبع C)

پرش بعدی در طول یک مسیر مینیمم منظم به LRL موجود در جهت مسیر مینیمم منظم، هدایت می‌شود. سه پی آمد ممکنه وجود دارد. اگر LRL کمتر یا برابر با قرارگیری بسته در آن جهت باشد، LRL در نظر گرفته می‌شود. اگر LRL بزرگتر از جابجایی بسته باشد، پس طول مسیر در طول LRL ، یک چرخش برابر با 180 درجه ایجاد می‌کند. این جابجایی با طول مسیر حول LRL قابل مقایسه است. هرکدام از این مسیرها که کوچکتر باشند، در نظر گرفته می‌شوند. تصمیم گیری های اتخاذ شده‌ی زیر در این سناریو انجام شده است (شکل 1b):
مقصد 1a:تنها مسیر مینیمم منظم به LRL متصل شده است. این مسیر مسیر مینیمیم غیر منظمی نیست. یا بسته باید از پورتی استفاده کند که در آن جا نگرفته است، یا این بسته باید LRL را در نظر بگیرد و چرخشی 180 درجه در نقطه‌ی خروج، ایجاد کند. پورت یا پورت های خروجی که به این مسیر دارای پرش های حداقل هستند و با رابطه‌ی مسیریابی، باز می‌گردند. در این مورد، مسیر متصل به LRL ، پرش های زیادی ایجاد می‌کنند زیرا این مسیر دور زده شده است. بنابراین، این بسته به طور عمود بر LRL مسیردهی می‌شود.
مقصد 1b. در روتورهای مسدود شده، یکی از پورت های خروجی برروی مسیر مینیمم منظم( در بسته) یک LRL را شروع می‌کنند. در این مورد، LRL در نظر گرفته می‌شود و این بسته به میزان 180 درجه می‌چرخند و نقطه‌ی خروج به مقصد 1a می‌رسد.
مقصد 1c: طول LRL برابر با جابجایی بسته در طول محور می‌باشد. بنابراین، LRL یک مسیر مینیمم به سمت مقصد است و در بسته قرار دارد.
مقصد 2: طول LRL بزرگتر از جابجایی بسته است و پورت دیگری بر روی مسیر مینیمم منظم وجود دارد.
برخی از تصمیمات توصیف شده، تنها برای اطمینان حاصل کردن از این موضوع است که هر روتور مسدود شده بتواند به حالت پورت های خروجی خود دستیابی داشته باشد و آن روتور ارسال کننده می‌تواند به حالت پورت های خروجی همسایه خود، دستیابی داشته باشد. ما در مورد ذخیره سازی این اطلاعات در بخش قبل صحبت کردیم. این اطلاعات، همراه با قیود قرارگیری، این اطمینان را ایجاد می‌کند که هر روتور مسدود شده بوسیله‌ی روتورهای نگهبان احاطه شده است. هر روتور نگهبان می‌تواند یک بسته بر روی مسیر مینیمم منظم، هدایت کند. این مسئله می‌تواند برای دو نوع آخر از موانع، ایجاد شوند زیرا پورت های مسدود شده بر روی تنها مسیر منظم، واقع شده اند.
حال که ما دیدیم که چگونه در الگوریتم ما این اطمینان حاصل می‌شود که تصمیم گیری های مسیریابی بهینه اتخاذ شده اند، ما استفاده از آنها را از طریق یک ارزیابی از مسیریابی، نشان دادیم. این کار در یک سیستم 14 در 14 شبیه سازی گردید.

ارزیابی

همانگونه که در بخش قبل بحث شد، هر جایی که یک LRL ایجاد شده است، روتورهای پیرامون آن یک جعبه‌ی مقید را تشکیل می‌دهند که در آن، LRL دیگر ممکن نیست قرار گیرد. این جعبه‌ی مقید همچنین دارای بخش هایی از شبکه است که در آن الگوریتم مسیریابی باید به طور انطباقی، کانال ها را انتخاب کند و بواسطه‌ی این انتخاب، عدد بسته هایی را که مسیرهای کوتاه تری را بر روی LRL انتخاب کرده اند، ماکزیمم می‌شوند. علاوه براین، عدد بسته هایی که پرش های اضافی را انتخاب کرده اند، مینیمم شده است. علت این موضوع وجود پورت های غیر فعال است. ما اکنون یک آنالیز بر روی الگوریتم مسیریابی ارائه کرده ایم. این کار با در نظر گرفتن تصمیم گیری های مسیریابی انجام شده است. این تصمیمات برای هر جفت منبع- مقصد از گره در داخل جعبه‌ی مقید، اتخاذ شده است. این آنالیز در نظر ندارد تا میزان تأثیر تکنیک قرارگیری LRL یا Bypass را مورد ارزیابی قرار دهد. علت این موضوع این است که این مقاله نشان داده است که یک چنین اتصال هایی می‌تواند تحت برخی شرایط، مفید باشد. برای مثال، کار ما نشان داده است که 74 تا 80 % از بسته ها که پورت خروجی روتر را ترک می‌کنند، دارای چرخش صفر درجه در آن روتر هستند. پس با این کار می‌توان میزان مصرف انرژی را کاهش داد. برهمکنش ما ایجاد یک آنالیز از رفتار الگوریتم مسیریابی در رژیمی است که در آن از حضور پیکربندی های توپولوژیک استفاده شده است.
با استفاده از یک شبیه ساز NoC سفارشی، ما LRL ها را با تغییر طول و ارسال بسته میان جفت منبع- مقصد ممکنه در داخل ناحیه‌ی قرارگیری، شبیه سازی کرده ایم. شکل 1 بخش دوم این مثاله، مثال هایی از LRL های با طول 2 و3 را نشان می‌دهد. برای هر جفت، ما تغییر در عدد پرش و طبقه بندی هر تصمیم مسیریابی را مشاهده می‌کنیم. این تصمیم گیری ها به دلیل وجود LRL، اتخاذ شده اند. ما نشان دادیم که اگر یک تصمیم گیری مسیریابی از طریق معادله‌ی هفتم، به سناریوی مسیریابی مرتبط شود، طبقه بندی به صورت زیر است:
LRL در طول مسیر: یک LRL برای بسته در پورت خروجی مناسب، قرار داده شده است. این پورت یک پورت منفرد برروی مسیر مینیمم منظم می‌باشد. به هر حال، بیشتر از دو پرش اضافی ایجاد می‌شود، اگر، LRL در نظر گرفته شود و چرخش بسته برابر با 180 درجه باشد. از این رو، بسته به سمت LRL انحراف پیدا می‌کند. این مسئله بوسیله‌ی سناریوی C – مقصد 2 در شکل 1b، نشان داده شده است.
LRL در میان مسیر: یک LRL به نحوی معرفی شده است که پورت هایی را مسدود می‌کند که بر روی مسیر مینیمم بین منبع و مقصد، قرار دارند. بسته به طور انطباقی مسیر دهی می‌شود تا بدین صورت از رسیدن آن در یک روتور، جلوگیری گردد. در این روتور تنها پورت موجود برروی مسیر بلوکه می‌شود. بسته هایی که این تصمیم مسیردهی را دریافت کرده اند، هیچ پرشی ایجاد نمی‌کنند. این مسئله در سناریوی B، شکل 1a نشان داده شده است.
LRL انتخاب: یک پورت خروجی منفرد بر روی مسیر مینیمم بسته وجود دارد و این پورت به سمت یک LRL هدایت می‌شود. الگوریتم مسیریابی تعیین می‌کند که LRL با کوتاه ترین مسیر انتخاب گردد. این مسیر از بسته بوسیله‌ی پرش های 1 به 1، کوتاه می‌شوند. در اینجا LRL طول پرش های l می‌باشد.
همپوشانی: یک بسته در منبعی تزریق می‌شود که بوسیله‌ی یک LRL، همپوشانی کرده است. این کار موجب می‌شود تا تنها پورت خروجی برروی مسیر مینیمم منظم، غیر فعال گردد. این بسته باید منحرف گردد و دو پرش خطا را برطرف کند. این مسئله در سناریوی A اتفاق می‌افتد. شکل 1a را ببینید.
180 درجه: یک مقصد بسته در طول LRL واقع شده است. در اینجا، الگوریتم مسیریابی تعیین می‌کند که در نظر گرفتن LRL و چرخش 180 درجه ای در نقطه‌ی خروج، کوتاه ترین مسیر برای بسته است. این تصمیم گیری بوسیله‌ی سناریوی C مقصد 1a و 1b در شکل 1b نشان داده شده است.
انتخاب LRL در طول مسیر: انتخاب تابعی که به طور انطباقی یک بسته را به یک گره مسیردهی کند و همچنین انتخاب یک LRL که مسیر بسته را به کوتاه ترین حالت تبدیل کند، یکی از مهمترین کارهاست. در این حالت، استفاده از تابع lookahead برای تشخیص یک روتور همسایه دارای یک چنین LRL است. این مسیر از بسته بوسیله‌ی l-1 پرش، کوتاه سازی می‌شود که در اینجا، LRL پرش با طول l می‌باشد.
در شکل 2، تصمیم های مسیریابی اتخاذ شده به عنوان یک درصد از تمام تصمیم های اتخاذ شده برای هر جفت منبع- مقصد از گره ها، نشان داده شده است. این مسئله موجب می‌شود تا رابطه ای میان رفتار الگوریتم مسیریابی و طوب LRL، مشاهده گردد. مشاهده‌ی ابتدایی این را نشان می‌دهد که 21- 24 % از جفت های منبع- مقصد دارای مسیرهای مختلفی هستند که این مسئله نیتجه ای از قرارگیری LRL است. 2.8 تا 5.0 درصد از این جفت ها دارای مسیرهای طولانی تر هستند و 6.9 تا 0.6 % نیز دارای مسیرهای کوتاه تر هستند. از بین این مسیرها، بیشتر آنها از نوع LRL هستند که در آنها تابع انتخاب از یک Lookahead استفاده می‌کند و بواسطه‌ی آن، اطمینان حاصل می‌کند که یک مسیر با هیچ خطا بوجود آمده است. این مشاهده می‌شود که وقتی طول افزایش می‌یابد، کسر تصمیم گیری های مسیریابی همپوشانی کرده، افزایش می‌یابد. این مسئله دو خطای پرش را ایجاد می‌کند. و این موضوع موجب افزایش و تمام شدن آنها می‌شود. این مسئله نشان می‌دهد که طولانی تر بودن LRL موجب می‌شود تا مینیمم کردن عدد بسته، مشکل تر شود. علت این مسئله این است که پورت های غیر فعال زیادی وجود دارد. مقدار تصمیم گیری های 180 درجه نیز ثابت می‌شوند زیرا تنها یک منبع وجود دارد و عدد مقصد ها برای یک چنین چرخشی، به طور خطی بقا افزایش طول مسیر، افزایش می‌یابد.
تغییر در طول مسیر برای هر جفت منبع- مقصد در شکل 4 خلاصه شده است. به دلیل اینکه ما تنها یک ناحیه‌ی ثابت در اطراف LRL را در نظر گرفته ایم، یک عدد ثابت از جفت های منبع- مقصد وجود دارد که این جفت ها می‌توانند در طول LRL مسیردهی شوند. به هرحال، صرفه جویی در هر جفت بوسیله‌ی طول مسیرتعیین می‌شود. بطور عکس، عدد جفت هایی موجب بروز خطا می‌شوند علت این مسئله این است که LRL به طول مسیر وابسته است اما خطا ثابت است. بنابراین، یک طول مسیر باید وجود داشته باشد که در آن، خطای کل بوسیله‌ی صرفه جویی کل، به تعادل برسد. برای LRL با بیش از 7 پرش، یک کاهش در طول مسیر متوسط میان تمام جفت های منبع- مقصد در گره ها، وجود دارد. این مسئله نشان می‌دهد که برای بارهای ترافیکی یکنواخت، یک طول مسیری که تا 7 پرش دارد، بهینه است. با افزایش طول LRL به بیش از 7 پرش، طول متوسط مسیر شروع به افزایش می‌کند زیرا کسر گره های منبعی همپوشانی کرده، به طور قابل توجهی از کسر LRL انتخاب شده، افزایش می‌یابد(شکل 2). این مسئله نشان دهنده‌ی این است که کارایی الگوریتمی که در آن توپولوژی می‌تواند به طور قابل توجهی تغییر شکل دهد، کاهش می‌یابد.
این مسئله باید بیان گردد که آنالیز بالا به طور کامل شاخصی از مزیت های کاربردی LRL ها در سیستم های NoC نیست. ما تنها یک زیر گروه از گره ها را در نظر گرفته ایم که قادرند به طور مؤثری از LRL استفاده کنند. این نتایج تنها می‌تواند تحت شرایطی مورد استفاده قرار گیرند که در آن مزیت ها در نظر گرفته شوند. این نتایج نشان می‌دهد که اگر شرایط ترافیکی به سرعت از حالت بهینه خارج گردد، الگوریتم مسیریابی هر خطایی را مینیمم می‌کند.

آنالیز نقطه‌ی نور

پیکربندی های دینامیک توپولوژیک، یک مش بندی غیر منظم ایجاد می‌کنند. این بخش ها دارای پورت های غیر فعالی هستند. تابع انتخابی که ما مورد استفاده قرار دادیم، قبل از این که خطر ایجاد گردد، در طول محور x می‌چرخند اما این پیکربندی ها به صورت انطباقی مسیریابی خواهند کرد اگر، یک LRL شماره‌ی پرش های یک بسته را کاهش دهد. این مسئله رفتارهایی را جایگزین می‌کند که دانسیته‌ی ترافیک را تغییر می‌دهند و وقتی این روش ها با الگوریتم های مسیریابی سنتی مورد مقایسه قرار می‌گیرد، یک چنین DOR ی بر روی یک شبکه‌ی با توپولوژی استاتیک و منظم، کار می‌کند. به عنوان یک مثال روشن کننده در زمینه‌ی الگوریتم Opt-bypass همراه با LRL، ما عملکرد آن را در حضور ترافیک جابجا شده، در نظر می‌گیریم. شکل 3 و جدول 1 نتایج استفاده از بافر را نشان می‌دهد. در این مثال بار شبکه به عنوان مصرف کل بافر در هر روتور در نظر گرفته شده است. یک الگوی ترافیکی جابجا شده بر روی یک شبکه‌ی با مش بندی 8 در 8، اجرا شده است که در ان، سرعت تزریق برابر با 0.009 بوده است. یک مش بندی منظم و استاتیک که از DOR استفاده می‌کند، برای مقایسه مورد استفاده قرار گرفته است. همچنین از یک شبیه ساز NoC سیکلی- قراردادی استفاده شده است. هر الگوریتم مسیریابی دارای تعداد کل 6 VC در هر کانال می‌باشد. ما این مسئله را در شکل 3b نشان دادیم. در این شکل اتصال های LRL مورد استفاده قرار گرفته اند تا بوسیله‌ی آنها ترافیک تحت این آزمون، مناسب باشد. نواحی سیاه رنگ نشان دهنده‌ی گره هایی هستندکه در آنها اشباع شوندگی بافر روتور کل، کم است و نواحی روشن نشاندهنده‌ی گره هایی است که در انها اشباع شوندگی بالاست. توجه کنیدکه قطر مرکزی شبکه های استاتیک دارای اشباع شوندگی کمتری هستند و از این رو جایگشت های ترانهادی در این گره ها به عنوان منبع، مورد استفاده قرار نگرفته اند. بافرهای N، E، S و W اشباع شوندگی بالایی دارند اما در کل، وجود LRL ها به همراه Opt-bypass دارای اثر قابل توجهی هستند. در حالی که ترافیک مسیردهی شده بوسیله‌ی DOR یک حالت یکنواخت ایجاد می‌کند، گرادیان متقارن دانسیته‌ی ترافیک از بالا سمت چپ و پایین سمت راست به سمت مرکز، از LRL ها برای توزیع مجدد ترافیک، استفاده می‌کند. در فرایند توزیع مجدد ترافیک، ترافیک هموارتراست. در فرایند توزیع مجدد ترافیک، برخی نقاط نورانی ایجاد می‌شود مخصوصا در اطراف محل های ابتدایی و انتهایی LRL. علت تشکیل این است که این عمل جاذب ترافیک می‌باشد. این جذب بوسیله‌ی قابلیت lookahead یک پرشی در این الگوریتم، ایجاد شده است. با استفاده از این جذب، مسیرهای اطراف پورت های ورودی LRL ، مینیمم می‌شوند. سپس، یک ازدحام متوسط در خروجی یک LRL ایجاد می‌شود زیرا ترافیک توده ای شده، باید تصمیم گیری هایی را با توجه به LRL موجود، اتخاذ کند. علاوه براین، برخی از بسته ها ممکن است چرخش های 180 درجه ای در خروجی، ایجاد کنند و موجب افزایش بار شوند.
به عنوان یک مثال، گره مسیریابی قرار گرفته در نقطه‌ی (2,3) را در نظر بگیرید. این گره یکی از متراکم ترین گره ها، تحت DOR و Opt-bypass هستند. تحت الگوریتم Opt-bypass، این گره یک ترافیک اضافی 59 % تحمل می‌کند که برابر با ترافیک 6 گره دیگر است. این ترافیک به دلیل قرارگیری آن، ایجاد شده است. در واقع اولا در ستون ها و سطرها ترافیک زیادی قرار گرفته و همچنین به دلیل وجود LRL در این بخشها، ترافیک زیاد است. این گره مجاور پورت غیر فعال و پورت ورودی LRL است. از آنجایی که این دانسیته در قرارگیری LRL موحب می‌شود تا برخی از بخش های ترافیکی مسیر خود را در مقایسه با مش منظم، تغییر دهند، گره های قرار گرفته در دانه های (2,3) دارای ترافیک اضافی هستند. بسته های خارج شده از گره های (0,4)، (1,4)، (2,4) ابتدا به سمت محور X مسیردهی می‌شوند. اما LRL که از نقطه‌ی (2,4) شروع می‌شوند، بسته هایی را حمل می‌کنند که از مقصدشان عبور می‌کنند. تابع انتخاب از عبور کردن این بسته به سمت LRL جلوگیری می‌کند و آنها را به نقطه‌ی (2,3) مسیردهی می‌کنند. با این کار عدد جریان های ترافیکی از میان گره های منفرد، افزایش می‌یابد.
در نظر گرفتن این شبکه به عنوان کل( همانگونه که در جدول 1 مشاهده می‌شود) موجب می‌شود تا اثر خالص الگوریتم Opt-bypass موجب شود تا میزات اشباع شوندگی بافر ورودی به میزان 5.4 % کاهش یابد. اثر جانبی این است که ترافیک به طور غیر یکنواخت توزیع مجدد پیدا می‌کند و انحراف بیشتری در اشباع شوندگی ایجاد می‌شود.
این واضح است که شبکه های دارای پیکربندی دینامیک بار را در مقایسه با توپولوژی های استاتیک، کاهش می‌دهند. در کل شبکه، یک کاهش متوسط برابر با 5.4 % در هر روتور مشاهده می‌شود اما برخی نقاط نورانی ایجاد می‌شود.

نتیجه گیری

ما یک الگوریتم مسیریابی با نام Opt-bypass برای شبکه های با مش بندی دینامیک غیر منظم پیشنهاده داده ایم که این الگوریتم از الحاق دینامیک یک تعداد دلخواه از اتصالات باند برد(LRL) حمایت می‌کند. این LRL ها دارای برخی قیود قرارگیری هستند. این الگوریتم بر اساس الگوریتم مسیریابی گودال کرمی با انطباق کامل ساخته شده است. و بنابراین Opt-bypass قادر است تا از توابع انتخابی استفاده کند که در آن ازدحام شبکه ای و توپولوژی محلی در نظر گرفته شده است. با استفاده از تکنیک های اثبات شده، نشان داده شده است که Opt-bypass دارای بن بست نیست.
در شبکه های دارای LRL هم پوشانی، این را نمی‌توان فرض کرد که یک کانال خروجی بر روی مسیر مینیمم (برای مش بندی منظم) برای مش بندی غیر منظم نیز مینیمم است. تکنیک جدید ما روابط مسیریابی به دو بخش تجزیه می‌کند: اولین بخش از داده های توپولوژی محلی برای محاسبه‌ی آن دسته از پورت هایی استفاده می‌کند که بر روی مسیر مینیمم غیر منظم واقع شده اند. و دومی بر روی هر محدودیت چرخشی اعمال می‌شود به نحوی که تنها آن کانال هایی که به بن بست نمی‌خورند، برای تابع انتخاب مهیا هستند. ما همچنین یک تابع انتخاب معرفی کردیم که از داده های توپولوژی محلی برای انتخاب انطباقی کانال هایی استفاده می‌کند که در ان عدد بسته ها مینیمم می‌شود. علاوه براین، تابع انتخاب همچنین عدد بسته هایی را افزایش می‌دهد که به LRL مسیردهی می‌شوند.
تکنیک ضمیمه ای LRL نیازمند این است که یک حلقه از روتورها با تمام پورت هایشان در حالت دیفالت، در اطراف هر روتور همپوشانی شده به وسیله‌ی یک LRL، قرار گیرند. ما رفتار انطباقی الگوریتم های مسیریابی را در زمانی که بسته های مسیردهی شده در میان جفت های منبع- مقصد انتقال می‌یابند، مورد بررسی قرار دادیم. این مشخص گردید که حتی اگر یک LRL در یک ناحیه‌ی با الگوی تزریق ترافیکی یکنواخت قرار گیرد، الگوریتم مسیریابی این اطمینان را حاصل می‌کند که در کل، یک کاهش در شمارش پرش ها میان تمام این جفت ها، وجود دارد( این مسئله برای پرش های کمتر و برابر با 7 صادق است). یک چنین شرایط ترافیکی زیر حالت بهینه است و نسبت به یک LRL نشان داده شده در مرجع 18، مزیت ندارد. ارزیابی ما نشان می‌دهد که این الگوریتم مسیریابی هر خطای ایجاد شده را تا زمانی که LRL حذف می‌شود، به حداقل می‌رساند. یک مثال از نحوه‌ی تغییر بار شبکه تحت توپولوژی دینامیک و با الگوریتم مسیریابی Opt-bypass ارائه شده است. اشباع شوندگی متوسط بافر ورودی به میزان 5.4 % کاهش یافته است و میزان کاهش کل در کل شبکه برابر با 6.5 % می‌باشد.

/ج